\documentclass[12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{graphicx}
\usepackage{vmumath}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{avo_book}
\usepackage{subcaption}
\usepackage[a4paper,left=15mm,right=15mm,top=30mm,bottom=20mm]{geometry}
\parindent=0mm
\parskip=3mm
\noaftermath
\pagestyle{empty}


\begin{document}



\section{Алгоритм поиска гамильтонова цикла}
Пусть нам дан простой граф $G=(V,E).$ Как найти в этом графе гамильтонов цикл, если он существует? Простейший подход состоит в следующем: начнём с произвольной вершины $v$ в графе и попробуем рекурсивно построить гамильтонов цикл из неё: переберём её соседей, для каждого из соседей переберём его соседей, отличных от $v$, и так далее. Если в результате при глубине рекурсии $n:=|V(G)|$ мы хоть раз попадём в соседа $v$, то пройденный путь можно дополнить до гамильтонова цикла. Такой подход в худшем случае требует $O^*(n!)$ времени, что очень неэффективно. Однако, одно достоинство у такого алгоритма всё-таки есть: алгоритм требует полином от $n$ памяти.

Чтобы ускорить предыдущий алгоритм, можно воспользоваться методом динамического программирования. В качестве подзадач возьмем задачи поиска простого пути, начинающегося в какой-то раз и навсегда фиксированной вершине $v_0$, оканчивающегося в вершине $v$ и проходящего через множество вершин $S$. Будем хранить в ячейке массива $dp[v,S]$ какой-нибудь путь с указанными характеристиками. Изначально известно, что $dp[v_0,\{v_0\}]=(v_0)$. Теперь, если мы хотим решить задачу для пары $(v,S)$, где $v \in S$, то нужно обойти всех соседей вершины $v$, и для каждого соседа (назовём его $u)$ проверить есть ли путь из $v_0$ в $u$, проходящий через $S\,\backslash \{v\}$. Если такой путь имеется, то положим $dp[v,S]:=dp[u,S\,\backslash \{v\}] + v$. После того, как все подзадачи решены, достаточно проверить, что существует простой путь из вершины $v_0$ в какого-нибудь её соседа $u$, проходящий через $V(G)$, и если такой путь есть, замкнуть его, образовав гамильтонов цикл. Решение одной подзадачи зависит от не более $n$ других подзадач, а общее количество подзадач — $n2^n$. Таким образом, время работы этого алгоритма относительно предыдущего алгоритма уменьшено и составляет $O^*(2^n),$ ценой экспоненциального расхода памяти.

Попытаемся решить другую задачу: по данному графу определить, является ли он гамильтоновым. На первый взгляд, эта задача проще предыдущей, так как сам гамильтонов цикл теперь предъявлять не надо. Однако при внимательном рассмотрении можно заметить, что если мы умеем эффективно решать эту задачу, то умеем решать эффективно и предыдущую. А именно, пусть A — алгоритм, работающий за время $T(n),$ использующий $M(n)$ памяти и по графу определяющий, является ли этот граф гамильтоновым. Сконструируем алгоритм, решающий задачу предъявления гамильтонова цикла таким образом: из данного графа $G$ будем последовательно удалять рёбра, убеждаясь с помощью алгоритма А, что удаление очередного ребра не нарушает свойство гамильтоновости. Как только настанет такой момент, что удаление любого ребра нарушает это свойство, можно будет заключить, что оставшиеся в графе рёбра и образуют гамильтонов цикл, который следует вывести в качестве ответа. Такой алгоритм работает за $O^*(T(n))$ и использует $O^*(M(n))$ памяти, так как количество запусков алгоритма А не превосходит количества рёбер в графе $G$.

Решить задачу определения того, является ли граф гамильтоновым, можно посчитав количество гамильтоновых циклов и сравнив это число с нулём. Пусть $X$ — все (не только простые) циклы длины $n$ в графе $G$. $A_i$ — все циклы длины $n$, не проходящие через вершину $i$. Тогда количество гамильтоновых циклов можно записать так: $|X|-|\bigcup_i A_i|$. Для подсчёта этого числа перепишем его в следующем виде, то есть применим принцип включения-исключения: 
$$
|X|-|\bigcup_i A_i| = \sum_{S \subseteq V(G) } (-1)^{|S|} \Bigl | \bigcap_{i \in S} A_i \Bigr |.
$$

Осталось понять, как вычислять значение выражения $ | \bigcap_{i \in S} A_i  |$ при данном $S$. Это выражение представляет собой количество циклов длины $n$, избегающих вершин из $S$. Чтобы вычислить его, используем динамическое программирование на графе $G-S$. Зафиксируем в этом графе вершину $v_0$. Пусть $dp[v,l]$ — количество путей (не обязательно простых) длины $l$, начинающихся в $v_0$ и заканчивающихся в  $v$. Изначально мы знаем, что $dp[v_0,1]=1$ и $dp[v,1]=0$ для всех остальных $v$. Пересчитывать эти значения легко:

$$
dp[v,l] = \sum_{(u,v)\in E(G-S)} dp[u, l-1].
$$
Также можно видеть, что 
$$
 | \bigcap_{i \in S} A_i  | = \sum_{(u,v_0)\in E(G-S)} dp[u, n],
$$
так как выражение в правой части есть в точности количество способов дополнить до цикла одним ребром некоторый путь, начинающийся в $v_0$ и содержащий $n$ вершин. Размер массива $dp$, как видно, составляет $n^2$. Таким образом, для каждого $S$ мы умеем вычислять количество циклов, избегающих $S$, за полиномиальное время. Число различных $S$ равно $2^n$, поэтому общее время работы алгоритма составляет $O^*(2^n)$, а расход памяти полиномиален: массив $dp$ можно переиспользовать после обработки очередного $S$. Мы получили эффективный по времени и экономный по памяти алгоритм для проверки графа на гамильтоновость.












\end{document}